"""
八皇后问题是经典的回溯算法应用，目标是在 8×8 的棋盘上放置 8 个皇后，使得任意两个皇后不能处于同一行、同一列或同一斜线上。


代码说明
1：核心思路：利用回溯法逐行放置皇后，每放置一个皇后就记录其所在的列和对角线，避免后续皇后冲突。若成功放置所有 8 个皇后，则记录当前方案。
2：冲突检测：
    列冲突：用集合cols记录已放置皇后的列索引，新皇后不能在集合中。
    主对角线冲突：主对角线上的点满足行-列=常数，用集合diagonals1记录该常数，新皇后的行-列不能在集合中。
    副对角线冲突：副对角线上的点满足行+列=常数，用集合diagonals2记录该常数，新皇后的行+列不能在集合中。
3：回溯过程：
    从第 0 行开始，尝试在当前行的每一列放置皇后。
    若当前列合法（无冲突），则记录位置并递归处理下一行。
    若递归完成后未找到合法方案，则撤销当前选择（回溯），尝试下一列。
4:输出：
所有合法方案以列表形式返回，每个方案是 8 个字符串，每个字符串代表一行棋盘（Q为皇后，.为空位）。八皇后问题共有 92 种解法，代码会打印解法总数和前 3 种示例。


八皇后问题共有 92 种解法

前3种解法示例：

解法 1：
Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....

解法 2：
Q.......
.....Q..
.......Q
..Q.....
......Q.
....Q...
.Q......
...Q....

解法 3：
.Q......
......Q.
....Q...
.......Q
Q.......
...Q....
..Q.....
.....Q..


"""


def solve_n_queens(n):
    """
    解决n皇后问题（此处n=8即八皇后）
    :param n: 皇后数量（棋盘大小n×n）
    :return: 所有合法摆放方案的列表，每个方案用'.'表示空位，'Q'表示皇后
    """

    def backtrack(row, path, cols, diagonals1, diagonals2):
        """
        回溯函数：尝试在当前行放置皇后
        :param row: 当前处理的行（从0开始）
        :param path: 已放置的皇后位置（每行一个，记录列索引）
        :param cols: 已占用的列集合（避免同列冲突）
        :param diagonals1: 已占用的主对角线集合（避免同主对角线冲突，行-列相同）
        :param diagonals2: 已占用的副对角线集合（避免同副对角线冲突，行+列相同）
        """
        # 基线条件：若已处理完所有行，说明找到一个合法方案
        if row == n:
            # 将path转换为可视化棋盘（每行用字符串表示）
            board = []
            for col in path:
                # 每行中，皇后位置为'Q'，其余为'.'
                board.append('.' * col + 'Q' + '.' * (n - col - 1))
            result.append(board)
            return

        # 尝试在当前行的每一列放置皇后
        for col in range(n):
            # 计算当前位置的主对角线和副对角线标识
            d1 = row - col  # 主对角线：行-列的值相同则在同一主对角线
            d2 = row + col  # 副对角线：行+列的值相同则在同一副对角线

            # 剪枝：若当前列或对角线已被占用，跳过该列
            if col in cols or d1 in diagonals1 or d2 in diagonals2:
                continue

            # 选择当前列放置皇后
            path.append(col)
            cols.add(col)
            diagonals1.add(d1)
            diagonals2.add(d2)

            # 递归处理下一行
            backtrack(row + 1, path, cols, diagonals1, diagonals2)

            # 回溯：撤销选择，尝试其他列
            path.pop()
            cols.remove(col)
            diagonals1.remove(d1)
            diagonals2.remove(d2)

    # 存储所有合法方案
    result = []
    # 从第0行开始回溯，初始状态为空
    backtrack(0, [], set(), set(), set())
    return result


# 测试八皇后问题
if __name__ == "__main__":
    # 求解八皇后（n=8）
    solutions = solve_n_queens(8)
    print(f"八皇后问题共有 {len(solutions)} 种解法")

    # 打印前3种解法（可选）
    print("\n前3种解法示例：")
    for i in range(min(3, len(solutions))):
        print(f"\n解法 {i + 1}：")
        for row in solutions[i]:
            print(row)